package com.hs;

import java.util.*;

/**
 * @Author: hs
 * @Description: 分而治之，递归思路
 * @Date: Create in 10:08 2019/1/23
 */
public class TestDC {
    public static void main(String[] args) {
        /*LinkedList<Integer>  links = new LinkedList<>();
        links.add(1);
        links.add(3);
        links.add(5);
        links.add(7);
        System.out.println(sum(links));*/
        List<Integer> lists =  new ArrayList<>();
        lists.add(31);
        lists.add(41);
        lists.add(22);
        lists.add(49);
        lists.add(55);
        lists.add(100);
        lists.add(30);
        lists.add(34);
        lists.add(80);
        lists.add(65);
        lists.add(99);
        List qsout = qsout(lists);
        qsout.forEach((i)->{
            System.out.println(i);
        });
        HashMap<String,String> a = new HashMap<>();
        String sss = a.put("sss", "222");
        System.out.println(sss);
    }

    private static Integer sum(LinkedList<Integer> links){
        if (links.size() < 2){
            return links.pollFirst();
        }else {
            return links.pollFirst() + sum(links);
        }
    }

    /**
     * 快速排序
     * @param lists
     * @return
     */
    private static List qsout(List<Integer> lists){
        if(lists.size()<2){
            return lists;
        }else {
            //选中间原始作为 基准值 比较好。如果选择第一个的话，原来列表本来就是排序的就出现最糟糕的情况了
            Integer pivot = lists.get(lists.size()/2);
            List<Integer> less = new ArrayList<>(lists.size());
            List<Integer> pivots = new ArrayList<>(lists.size());
            List<Integer> greater = new ArrayList<>(lists.size());
            lists.forEach((i)->{
                if(i<pivot){
                    less.add(i);
                }else if(i>pivot){
                    greater.add(i);
                }else{
                    pivots.add(i);
                }
            });
            List<Integer> sumList = new ArrayList<>();
            sumList.addAll(qsout(less));
            sumList.addAll(pivots);
            sumList.addAll(qsout(greater));
            return sumList;
        }

    }

}
